package 动态规划专项训练.动态规划训练1;

/**64.最小路径和
 * 求最值型动态规划
 * @author zx
 * @create 2022-03-30 23:21
 */
public class Num64 {
    public int minPathSum(int[][] grid) {
        if(grid.length == 0 || grid[0].length == 0){
            return 0;
        }
        int m = grid.length;
        int n = grid[0].length;
        int[][] f = new int[2][n];
        int old = 1,now = 0;
        int t1,t2;
        for(int i = 0;i < m;i++){
            old = now;//old是i - 1行
            now = 1 - now;//now 是 i 行
            //为啥now = 1 - now：  1 - 1 = 0;1 - 0 = 1实现滚动
            for(int j = 0;j < n;j++){
                if(i == 0 && j == 0){
                    f[now][j] = grid[i][j];
                    continue;
                }
                f[now][j] = grid[i][j];
                if(i > 0){
                    t1 = f[old][j];
                }else{
                    t1 = Integer.MAX_VALUE;
                }
                if(j > 0){
                    t2 = f[now][j - 1];
                }else{
                    t2 = Integer.MAX_VALUE;
                }
                if(t1 < t2){
                    f[now][j] += t1;
                }else{
                    f[now][j] += t2;
                }
            }
        }
        return f[now][n - 1];
    }
}
